There are many situations in which a user may wish to search for a digital image. For example, a user may wish to look for a particular digital picture on the Internet. As another example, a user may wish to retrieve a particular digital image from a set of digital images the user has stored locally on the user's personal computer. As a result, many different types of software applications have a need to support functionality that enables a user to search for digital images.
While several different approaches exist for retrieving digital images, these approaches are not without limitations. One approach for performing a search for a digital image (denoted the “query by keyword” approach) is to search for all digital images in a set of digital images that are associated with a character string that matches one or more search terms (referred to individually as a “keyword”) submitted by a requesting user. For example, if a user submits a query having a keyword “dog,” and the term “dog” is in the name of a particular digital name, then this approach might suggest that the digital image that has the word “dog” in its name satisfies the query.
A problem with the query by keyword approach is that, for a digital image to satisfy the query, a keyword identified in the query needs to match a character string associated with the digital image. Users are free to assign any name and/or description to a digital image based on any reason. A user may decide to assign a name and/or description to an entire digital image for purposes of describing the visual content of the digital image, but also based on subjective, spatial, temporal and social reasons. For example, the name or description of a digital image may be assigned, either by a human or software entity, based on a timestamp, the name of a folder containing the digital images, or a sequence number indicating the position of the digital image relative to other digital images. This complicates the task of keyword based search, as a particular digital image, which might otherwise satisfy the user's query, might be associated with text that does not match any of the keywords identified by the query.
Another problem with the query by keyword approach is that a series of keywords simply lacks the expressiveness that is inherent in a digital image. In other words, it is difficult for a user to express the visual characteristics of the desired image only using only a few keywords.
Another approach (denoted the “query by image approach”) for performing a search for a digital image is to search for all digital images in a set of digital images that are similar to a sample digital image that is submitted by the requesting user. An initial obstacle with the query by image approach is that the requesting user must use a sample digital image to find other images, and in many instances the requesting user simply may not have a sample digital to use as a basis for the search.
Another problem of the query by image approach is that it can be difficult to identify the other digital images that are similar to the sample digital image submitted by the requesting user. This is caused by a phenomenon known as the semantic gap problem. The semantic gap problem characterizes the difference between two descriptions of an object by different linguistic representations. In the query by image approach, high level concepts (such as a flag, an airplane, or a newsreader) are derived from the low level features (such as color of an object, shape of an object, or size of an object) that are extracted from the sample digital image submitted by the requesting user. Thus, if the high level concepts present in the appearance of a digital image are to be identified to understand the meaning of the digital image, the only available independent information is the low-level pixel data for the digital image. However, even the simple linguistic representation of shape or color such as round or yellow requires entirely different mathematical formalization methods. Due to this complexity, it is often difficult to determine which high level features of the user-submitted sample digital image the user is interested in, and it is next to impossible to build specific high level concept detectors for all concepts in the physical world.
Accordingly, a new improvement in the field of digital image search would be desirable. The approaches described in this section are approaches that could be pursued, but not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated, it should not be assumed that any of the approaches described in this section qualify as prior art merely by virtue of their inclusion in this section.